package foundation.graph;

import java.util.Arrays;

// 链式前向星 建图
public class graphBuild {
    /*
     链式前向星:
          head[i] 代表 i 点的第一条边 next[head[i]] 为该点的第一条边

          如果 i 点没有边，那么 head[i] = 0,如果 i 点有边，那么 head[i] = 边号

          next[i] 代表 i 点的下一条边
          如果 i 点没有边，那么 next[i] = 0,如果 i 点有边，那么 next[i] = 下一条边号

          对于一个点而言 head[i]  中的 i 为该点的遍号  它的变为 head[i]  以及next[head[i]]  next[next[head[i]]] ...... 直到next[i]为0

          对于每一条边 而言 to[i] 为 该边去往的点   它的起点为 最开始的边的 head[i] 中的 i 的值
     */

    public static int MAXN = 10001;

    // 索引为 点号  值为 该点的第一个边
    public static int[] head = new int[MAXN];

    // 索引为 边号  值为 下一条边号
    public static int[] next = new int[MAXN];

    // 索引为 边号  值为 去往的点
    public static int[] to = new int[MAXN];

    // 索引为 边号  值为 权重
    public static int[] weight = new int[MAXN];

    // 边的遍号
    public static int cnt;

    // 点的个数
    public static int n;

    /**
     * 建立图
     *
     * @param n 表示点数
     *          由于将cnt重置后
     *          将 head 数组初始化为 0
     *          在该点新建一个边的时候 next[cnt] = head[u]; 此时head[u] = 0
     *          所以 之前的不会影响新建立的边
     *          <p>
     *          所以 可以保证不会出现 边重叠的情况,仅需要对 head 数组进行初始化
     */
    private static void build(int n) {
        cnt = 1;
        Arrays.fill(head, 1, n + 1, 0);

    }

    // 加边
    private static void addEdge(int u, int v, int w) {
        // u -> v  权重为 w
        next[cnt] = head[u];
        to[cnt] = v;
        weight[cnt] = w;
        head[u] = cnt++;
    }

    private static void display() {
        for (int i = 1; i <= n; i++) {
            System.out.print(i + "(邻居,边权) : ");
            for (int ei = head[i]; ei > 0; ei = next[ei]) {
                System.out.print("(" + to[ei] + "," + weight[ei] + ") ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        n = 5;
        int[][] arr = new int[][]{
                {1, 2, 3},
                {1, 3, 4},
                {2, 3, 5},
                {2, 4, 6},
                {3, 4, 7},
                {4, 5, 8}
        };
        build(n);

        for (int[] edge : arr) {
            addEdge(edge[0], edge[1], edge[2]);
        }
        display();
    }


}
